【题解】 [BOI2007]Mokia CDQ分治 luogu4390 | Qiuly's blog!

【题解】 [BOI2007]Mokia CDQ分治 luogu4390

Posted on | Edited on | In | Comments:

BBQ烤翅，CDQ分治。

一道很裸的三位偏序，允许离线的话，就上CDQ分治，当然想当码农可以敲树套树。

很显然，三维就是 $x$ 轴，$y$ 轴，和时间。

然后将一个矩阵的询问拆成四个询问，按照容斥的方式搞，这显然是可以且简单的，但是询问数将会爆炸 $QvQ$ (但是没有炸，不舒服)

$long long$ 也要开，不然会炸。

然后就这样了。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>

#define ll long long
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))

const ll N=2e6+2;
const ll inf=1e9+9;

ll s,w,tot,c[N];
struct Node{
    ll x,y,ans,pos,type;
}q[N],hep[N];
bool cmp(const Node&x,const Node&y){return x.pos<y.pos;};

struct BIT{
    void add(ll x,ll v){for(;x<=w;x+=(x&-x))c[x]+=v;};
    ll sum(ll x){ll res=0;for(;x;x-=(x&-x))res+=c[x];return res;};
    void clr(ll x){for(;x<=w;x+=(x&-x))c[x]=0;};
}T;

void CDQ(ll l,ll r){
    if(l==r)return;
    int mid=(l+r)>>1;
    CDQ(l,mid);CDQ(mid+1,r);
    ll i=l,j=mid+1,cnt=l;
    /*CDQ的主要流程*/
    while(i<=mid&&j<=r){
        if(q[i].x<=q[j].x){
        /*注意这一题询问和修改是不一样的，不像陌上花开那题，每个元素即使修改对答案做贡献，也是询问*/
            if(!q[i].type)T.add(q[i].y,q[i].ans);/*这是修改，树状数组标记一下*/
            hep[cnt++]=q[i++];/*归并排序*/
        }else{
            if(q[j].type)q[j].ans+=T.sum(q[j].y);/*询问，更新答案*/
            hep[cnt++]=q[j++];
        }
    }	
    /*将剩下的元素排序好，更新好答案*/
    while(i<=mid){
        if(!q[i].type)T.add(q[i].y,q[i].ans);
        hep[cnt++]=q[i++];
    }
    while(j<=r){
        if(q[j].type)q[j].ans+=T.sum(q[j].y);
        hep[cnt++]=q[j++];
    }
    for(ll o=l;o<=mid;++o)/*清除本次操作在树状数组上留下的痕迹*/
       if(!q[o].type)T.clr(q[o].y);
    for(ll o=l;o<=r;++o)q[o]=hep[o];/*更新原数组*/
}

int main(){
    ll op;
    scanf("%lld%lld",&s,&w);
    while(scanf("%lld",&op),op^3){
        ll x,y,z,x1,x2,y1,y2;
        if(op==1){
            scanf("%lld%lld%lld",&x,&y,&z);
            q[++tot]=(Node){x,y,z,tot,0};
        }else{
            scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
            /*四个询问*/
            q[++tot]=(Node){x2,y2,0,tot,1};
            q[++tot]=(Node){x1-1,y2,0,tot,1};
            q[++tot]=(Node){x2,y1-1,0,tot,1};
            q[++tot]=(Node){x1-1,y1-1,0,tot,1};
        }
    }
    CDQ(1,tot);
    std::sort(q+1,q+tot+1,cmp);
    for(ll i=1;i<=tot;++i) 
        if(q[i].type){
            printf("%lld\n",q[i].ans-q[i+1].ans-q[i+2].ans+q[i+3].ans+s*(q[i].y-q[i+3].y)*(q[i].x-q[i+3].x));
            i+=3;
            //printf("%lld\n",q[i].ans);
        }
    return 0;
}

然而我还是太弱了，调半个小时的原因既然是

树状数组打错了

$QvQ$

本文标题:【题解】 [BOI2007]Mokia CDQ分治 luogu4390

文章作者:Qiuly

发布时间:2019年02月22日 - 00:00

最后更新:2019年03月29日 - 13:55

原始链接:http://qiulyblog.github.io/2019/02/22/[题解]luoguP4390/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。